343. 整数拆分

链接：https://leetcode-cn.com/problems/integer-break/

题目分析

这道题稍微的写出来就可以得到下面这样子一棵树：

这又是一个递归解决问题的思路，然后和前面一样，我们通过发现递归问题中具有重叠子问题，所以我们使用动态规划自下而上的解决问题。

答案

理解了上面分解的思路实际上问题就非常简单了，还有一点需要注意的是，有可能不一定需要分解，比如3 sums(2) 和 3 2 ,明显前者是3而后者是6，所以这种情况是不用继续向下分的。所以考虑这个情况进去即可，在求max的时候加入即可。

class Solution:
    def integerBreak(self, n: int) -> int:
        sums = [0, 1]
        for i in range(2, n+1):
            tmp = 0
            for j in range(1, i):
                tmp = max(tmp, j * sums[i - j], j * (i - j))
            sums.append(tmp)
        return sums[n]

可以看到动态规划算法效果是非常好的。